// 给定一个正整数n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少
// 分割情况 n -> [n-1, 1]  n-1 < n
// n -> [n-2, 2]  2*(n-2)>n -> n > 4。
// 所以大于4的部分应该被切分，切分后乘积大于原始结果 分割因子可以取 2, 3, 4 n=9
// -> [4,4,1] n=9 -> [3,3,3] 3为最合适的分割因子 贪心准则
// 1. 如果n>4 则必须将其
#include <cmath>
#include <iostream>
using namespace std;
int maxProductCutting(int n) {
  if (n < 4) {
    return (n - 1);
  }
  int count_3 = n / 3;
  int remainder = n % 3;
  int count_2 = 0;
  // 计算3的个数 2的个数 和 1的个数
  if (remainder == 1) {
    count_3--;
    count_2 = 2;
  }
  if (remainder == 2) {
    count_2 = 1;
  }
  return pow(static_cast<float>(3), static_cast<float>(count_3)) *
         pow(static_cast<float>(2), static_cast<float>(count_2));
}

int main() {
  int n = 8;
  int maxProduct = maxProductCutting(8);
  cout << maxProduct << endl;
  return 0;
}